package code;

public class Code208 {
	class TrieNode {
	    // Initialize your data structure here.
        char c;
        boolean isWord;
        TrieNode[] children;
	    public TrieNode() {
        	c=0;
        	isWord=false;
        	children=new TrieNode[26];
	        for(int i=0;i<26;i++){
	        	children[i]=null;
	        }
	    }
	    
	    public TrieNode(char x) {
        	c=x;
        	isWord=false;
        	children=new TrieNode[26];
	        for(int i=0;i<26;i++){
	        	children[i]=null;
	        }
	    }
	}
	
    private TrieNode root;

    class Trie{
	    public Trie() {
	        root = new TrieNode();
	    }
	
	    // Inserts a word into the trie.
	    public void insert(String word) {
	        TrieNode p=root;
	        int len=word.length();
	        
	        for(int i=0;i<len;i++){
	        	int off=word.charAt(i)-'a';
	        	if(p.children[off]==null){
	        		TrieNode node=new TrieNode((char)(off+'a'));
	        		p.children[off]=node;
	        	}
	        	p=p.children[off];
	        }
	        p.isWord=true;
	    }
	
	    // Returns if the word is in the trie.
	    public boolean search(String word) {
	    	TrieNode p=root;
	        int len=word.length();
	        
	        for(int i=0;i<len;i++){
	        	int off=word.charAt(i)-'a';
	        	if(p.children[off]==null){
	        		return false;
	        	}
	        	p=p.children[off];
	        }
	        
	        return p.isWord;
	    }
	
	    // Returns if there is any word in the trie
	    // that starts with the given prefix.
	    public boolean startsWith(String prefix) {
	    	TrieNode p=root;
	        int len=prefix.length();
	        
	        for(int i=0;i<len;i++){
	        	int off=prefix.charAt(i)-'a';
	        	if(p.children[off]==null){
	        		return false;
	        	}
	        	p=p.children[off];
	        }
	        return true;
	    }
    }
}
